1038F - Wrap Around - CodeForces Solution

// LUOGU_RID: 91728575
#include<cstdio>
#include<cstring>
int n,m,g[45];
char st[45];
long long dp[45][45][2],ans=0;
int main()
{
scanf("%d",&n);
scanf("%s",st+1);
m=std::strlen(st+1);
for (int i=1;i<=m;i++)
{
int flag=1,x=1,y=i;
while (y<=m){if (st[x]!=st[y]) flag=0;++x,++y;}
g[i-1]=flag;
}
dp[1][1][1]=1;
for (int i=2;i<=n;i++)
for (int x=1;x<i;x++)
for (int o=0;o<=1;o++)
{
if ((i-x>=m||g[i-x])&&(n+1-i>=m||g[n+1-i])) dp[i][i][1-o]=dp[i][i][1-o]+dp[i-1][x][o];
dp[i][x][o]=dp[i][x][o]+(1+(x+m<=i))*dp[i-1][x][o];
}
for (int x=1;x<=n;x++) ans=ans+(dp[n][x][1]-dp[n][x][0])*(n+1-x);
printf("%lld\n",ans);
return 0;
}